/**
 * @program: LeetCode
 * @description: LeetCode : 844. 比较含退格的字符串
 * @author: WXY
 * @create: 2023-02-11 19:09
 * @Version 1.0
 **/
public class Num844_backspaceCompare {
    public static boolean backspaceCompare1(String s, String t) {
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        String stringS = process1(chars);
        String stringT = process1(chart);
        if (stringS.equals(stringT)) {
            return true;
        }
        return false;
    }

    private static String process1(char[] str) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            if (str[i] != '#') {
                sb.append(str[i]);
            } else {
                if (sb.length() != 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return sb.toString();
    }



    public static boolean backspaceCompare(String s, String t) {
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        String stringS = generate(chars);
        String stringT = generate(chart);
        if (stringS.equals(stringT)) {
            return true;
        }
        return false;
    }

    private static String generate(char[] str) {
        int index = 0;
        if (str.length == 1) {
            return new String(str);
        } else {
            for (int i = 0; i < str.length; i++) {
                if (str[i] != '#') {
                    str[index++] = str[i];
                } else {
                    if (index > 0)index--;
                }
            }
        }
        return new String(str,0,index);
    }

    public static void main(String[] args) {
        String s = "a##c";
        String t = "#a#c";
        boolean b = backspaceCompare(s, t);
        System.out.println(b);
    }
}
